package main.java.indi.zyj.hot100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _50_letterCombinations {

    List<String> res = null;

    StringBuilder stringBuilder = null;

    public List<String> letterCombinations(String digits) {

        if (digits == null || digits.length() == 0) return res;

        String[] str = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        res = new ArrayList<>();
        stringBuilder = new StringBuilder();

        backTrack(digits, str, 0);

        return res;
    }

    private void backTrack(String digits, String[] str, int index) {

        if (digits.length() == index) {
            res.add(stringBuilder.toString());
            return;
        }

        String s = str[digits.charAt(index) - '0'];
        for (int i = 0; i < s.length(); i++) {
            stringBuilder.append(s.charAt(i));
            backTrack(digits, str, index + 1);
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }

    }


}
